package com.solming.leetcode.question;

//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
//
//如果数组中不存在目标值 target，返回[-1, -1]。
//
//进阶：
//
//你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class SearchRange34 {

    public static int[] searchRange(int[] nums, int target) {

        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int leftIndex = range(nums,target,true);
        int rightIndex = range(nums,target,false);

        return new int[] {leftIndex,rightIndex};

    }

    public static int range(int[] nums,int target,boolean lower){
        int left = 0;
        int right = nums.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = nums[mid];
            if (val == target ) {
                index = mid;
                if (lower){
                    right=mid-1;
                }else{
                    left = mid+1;
                }
            } else if (target > nums[mid]) {
                left = mid+1;
            } else if (target < nums[mid]) {
                right = mid-1;
            }
        }
        return index;
    }


    public static void main(String[] args) {
        int [] arr = new int[]{5,7,7,8,9,10};
        int target = 8;
        int[] result = searchRange(arr,target);


    }

}
